The invention relates in general to the field of computer network communications and, more particularly, to a method for fairly allocating transmission bandwidth in a shared-media packet-switched network.
As originally designed and implemented, cable television (CATV) systems used only coaxial cable between a head-end controller, or distribution station, and the customer. Newer cable systems tend to be hybrids of fiber optics and coaxial cable; optic fiber being used for long distance distribution and coax being used for the last few thousand feet into individual customer sites. FIG. 1 shows a hybrid fiber-coax (HFC) system 100 comprising a head-end controller 105 connected via one or more fiber optic links 110 to a fiber-to-coax conversion unit 115 which, in turn, feeds a coaxial cable distribution network 120 running into a number of individual user or customer sites (e.g., homes 125). Cable television systems with this general type of hardware layout are fairly typical in the art today.
Cable systems originally provided uni-directional transfer of programming from the head-end controller 105 to the customer 125. With the growth of computer networks and a desire to provide a real-time interactive services to the customer, the need for an efficient means to provide two-way communication over an existing HFC network type network exists. A number of services providers currently furnish two-way services over cable. In these services there is generally a modestly high bandwidth link from the head-end controller to the user site. However, the link in the other direction, from the user""s site to the network, is through conventional dial-up facilities such as a modem or an integrated services and data network (ISDN) connection, which commonly have a much lower bandwidth than the head-end-to-user-site link. Such systems allow the customer to quickly download material from the network into their local machine (e.g., a personal computer or, more generally, a terminal equipment), but does not readily permit the user to originate any significant transmissions.
One way of enabling customers to originate significant transmissions is to permit them to use the cable system, which has a comparatively high bandwidth, for such transmissions. Within existing HFC networks, providing customers with the ability to transmit data upstream requires service providers (those organizations that operate head-end stations) to reserve sections of cable spectrum, i.e., bandwidth, for data services, and also to provide a mechanism for allocating that bandwidth to upstream users. As shown in FIG. 2, reserved bandwidth can be used to create virtual downstream 200 and upstream 205 channels. In this manner downstream and upstream data is (frequency) multiplexed over a single physical transmission cable 120 between one or more customer sites (via terminal equipment 210 such as a cable modem or a television set-top box) and a head-end controller 105 via a fiber-to-coax conversion unit 115.
FIG. 3 is a block diagram of a generic communication network 300 comprising a bandwidth allocation unit (BAU) 305, a physical communications network 310, and a plurality of network access units (NAUs) 315. Like to head-end controller 105, a bandwidth allocation unit is responsible for allocating downstream bandwidth (i.e., transmission from or through a bandwidth allocation unit 305 toward a network access unit 315 or customer/user site) and upstream bandwidth (i.e., transmission from a network access unit 315 or customer/user site toward a bandwidth allocation unit 305) over the network 310. In particular, a bandwidth allocation unit 305 is responsible for processing requests for transmission bandwidth from network access units 315 (such as, for example, a user""s terminal equipment 210). A network access unit 315 can be, for example, a terminal equipment 210 such as a personal computer located at a customer""s site.
The following alphabetical list of definitions and accompanying discussion, regarding various aspects of network characteristics and bandwidth allocation, are provided for the benefit of the reader.
ATM. Asynchronous Transfer Mode, which generally refers to a very specific telecommunications xe2x80x9cprotocol,xe2x80x9d discussed at the end of Section 1.3.
Authorization. Permission issued by a bandwidth allocation unit (BAU) to either a single network access unit (NAU) or a group of network access units that grants or permits use of the network access unit to bandwidth allocation unit (i.e., upstream) transmission resource during a specific time period. The case of the bandwidth allocation unit issuing permission to a single network access unit is called a xe2x80x9cdirected grant,xe2x80x9d when permission is issued to multiple network access units it is called a xe2x80x9ccontention grant.xe2x80x9d Authorizations are xe2x80x9cuse it or lose it.xe2x80x9d See also the discussion of Grant, below.
Bandwidth Allocation Unit (BAU). The collection of those bandwidth allocation functions co-located within a head-end controller responsible for the scheduling and allocation of transmission resources for both the downstream and the upstream channels of the shared media.
Class of Service. Even though the quality of service (QoS, see below) requirements of users may vary over a continuous spectrum of values, a network can only handle a restricted set of QoS classes corresponding to specific objective values of the relevant network performance parameters.
The ITU (International Telecommunications Union) specifies the following QoS classes in Recommendation I.371.
1. Deterministic Bit Rate (DBR): Traffic conformance is based on peak cell rates (PCR) and is characterized by low cell delay variation (CDV) and low cell loss ratio (CLR).
2. Statistical Bit Rate (SBR): Traffic conformance is based on a sustainable cell rate (SCR), a burst size and a PCR and is characterized by a medium to large CDV and low CLR.
3. Available Bit Rate (ABR): Traffic conformance is based on dynamic feedback of the actual capacity available within the network. Sources may always send at a signaled/negotiated minimum cell rate (MCR) and must never send at more than the PCR. This service type is characterized by large CDV, variable CTD, and low CLR.
The ATM Forum has adopted the ITU""s classes and has further added the following service classes.
1. Deterministic bit rate is designated as constant bit rate (CBR).
2. Statistical bit rate is designated as variable bit rate (VBR).
3. Real-Time Variable Bit Rate (rt-VBR): Traffic conformance is based on a sustainable rate, a burst size and a peak rate. This service is characterized by a low CDV and low CLR.
4. Unspecified Bit Rate (UBR): Traffic conformance is based on the peak cell rate and can have potentially very large CDV and CLR.
The IETF (Internet Engineering Task Force) has defined the following service classes.
1. Real-Time: Traffic conformance is based on a token bucket with a sustainable rate, and a bucket size; peak rate is assumed to be the line rate. Real-time services are characterized by low packet delay variation and very low packet loss.
2. Predictive: Traffic conformance is based on a token bucket with a sustainable rate and a bucket size; peak rate is assumed to be the line rate. Predictive services"" are characterized by medium packet delay variation and low (but larger than that of real-time) packet loss.
3. Best Effort: No traffic conformance. Characterized by large packet delay variation and a potentially large packet loss.
FIFO. First-In, First-Out, a method of managing a queue of items, referred to at the end of Section 1.3.
Flow. For the purposes of this document, a flow is a set of packets traversing a network or subnetwork all of which are covered by the same request for control of quality of service. At a given network element a flow may consist of the packets from a single application session, or it may be an aggregation comprising the combined data traffic from a number of application sessions.
Flow Identifier. A flow identifier uniquely identifies a packet as belonging to a flow. Examples of flow identifiers are ATM VCs, IPv6 flow identifiers, IPv4 from: less than IP address, protocol, port greater than , to: less than IP address, protocol, port greater than  pairs, or a  less than NAU id, QoS class greater than  pair. In the case of a  less than NAU id, QoS class greater than  pair being used as a flow identifier, the network access unit may be multiplexing multiple application-level flows onto the flow identifier user by a bandwidth allocation unit-network access unit pair. For the purpose of this document it is the knowledge of the flow identifier by a bandwidth allocation unit for a flow that is relevant.
Grant. A transmission form the bandwidth allocation unit (BAU) 305 to network access units (NAUs) 315 specifying one or more time/space slots in which particular network access units can transmit. All active network access units 315 scheduled by a bandwidth allocation unit are required to receive and process the grants from that bandwidth allocation unit 305. See also the discussion of Authorization, above.
Head-end controller. See Section 4.2, note [3].
HFC. Hybrid fiber-coax, a type of communications network including both fiber-optic cable and coaxial cable, discussed at the beginning of Section 4.1.
Multiplexing. Multiplexing can be viewed as a layer function which maps some number of upper layer tributary associations onto a single lower layer aggregate association. In terms of the ISO layer model, a multiplexing point is an N-layer function which aggregates one or more N+1 layer tributaries onto an N-layer tributary.
Network Access Unit (NAU). The collection of those bandwidth access functions necessary to (1) (possibly) aggregate traffic; (2) make requests of the bandwidth allocation unit 305; and (3) receive authorizations and transmit based on those authorizations.
Network Element. Any component of an internetwork which directly handles data packets and thus is potentially capable of excercising quality of service control over data flowing through it. Network elements include ATM switches, packet switches, routers, subnetworks, and end-node operating systems.
Protocol. In this context, a protocol is a method of transmitting information in which specific information is transmitted in a specific sequence and/or at specific times. A very simple example of a protocol is the 1-plus method of dialing a long-distance phone call, in which a 1 at the beginning of a dialed phone number indicates that a long-distance call is being made; the next three digits in the phone number indicate the area code to which the call is being made; and the last four digits indicate the local phone number being called.
Quality of Service (QoS). Quality of service requirements are specified in terms of objective values of network performance. These network performance parameters may include, for example, packet loss ratios, transfer delays, and delay variations. For ATM networks performance parameters are specified in Recommendation I.356 and include cell loss ratio (CLF), cell transfer delay (CTD), and cell delay variation (CDV).
Traditionally, the Internet has offered a single QoS; best-effort delivery with available bandwidth and delay characteristics dependent on instantaneous load. Control over the QoS seen by applications is exercised by adequate provisioning of the network infrastructure. In contrast, a network with dynamically controllable QoS allows individual application session to request network packet delivery characteristics according to their perceived needs, and may provide different qualities of service to different applications. It will be understood by one of ordinary skill in the art of computer network design and administration that there is a range of useful possibilities between the two endpoints of providing no dynamic QoS control at all and providing extremely precise and accurate control of QoS parameters.
Request. A network access unit (NAU) to bandwidth allocation unit (BAU) message which requests transmission resources in the direction from the network access unit 315 to the bandwidth allocation unit 305 (i.e., the xe2x80x9cupstreamxe2x80x9d direction). Requests for transmission resources at an N-layer entity can be generated explicitly from an N+1-layer request or implicitly by the arrival of N+1-layer traffic at the N-layer entity.
Shared Media. Any media such that (1) the bandwidth allocation unit 305 schedules the entirety of the transmission, and can transmit to any single network access unit 315, or group of network access units 315, or to the entire plurality of network access units 315 linked to that bandwidth allocation unit 305, and (2) the bandwidth allocation unit 305 explicitly authorizes any single network access unit 315, or group of network access unit 315, access to the media for transmission from the network access unit 315 to the bandwidth allocation unit 305.
Terminal equipment. See Section 4.2, note [3].
Virtual scheduling time. A value used in assigning priority to transmission requests, discussed in Section 4.2, notes [5] and [9], and in Section 4.3.
Weighted fair queuing. A method of allocating resources, discussed in Section 1.4.
Because of network topology, cable length, and electrical factors, transmission techniques such as the Ethernet""s carrier-sense multiple access with collision detection (CSMA-CD) do not work well in a hybrid fiber-coax (HFC) environment. Other bandwidth sharing schemes such as the IEEE 802.6 Distributed Queued Dual Bus (DQDB) standard or the ANSI X3.139-1987/ANS X3.148-1988 Fiber Distributed Data Interface (FDDI) standard require point-to-point links between each consecutive pair of user or terminal equipment sites. This requirement results in less than optimal use of ratio frequency (RF) spectrum or bandwidth on the physical cable, making it very difficult to provide for the numbers of end systems (e.g., users or terminal equipment sites) which must be served on a single cable segment 120. Such ring architectures are also not ideal for public services since they depend on every node in the network (or sub-network) being operational and functioning correctly.
One scheme known to work on a cable system is to assign transmission resources on a fixed increment basis, allowing each terminal equipment 310 (or other network access unit 315) to transmit only within its allocation, such as is seen in a fixed time domain multiplexed access (TDMA) method where terminals are assigned fixed slots in which to transmit. The same can be seen in a frequency domain multiple access (FDMA) method were terminals are assigned frequencies on an exclusive-use basis. For fixed bandwidth applications, these methods are often quite efficient. However, for non-fixed bandwidth applications, such as Internet traffic or variable-rate video traffic, the use of TDMA or FDMA methods can be wasteful of bandwidth. That is, the TDMA and FDMA methods may divide available bandwidth inefficiency when a terminal equipment""s bandwidth requirements vary in time.
Many applications (i.e., processes executing at a terminal equipment 210 or other network access unit 315) can operate with whatever bandwidth they are given and can usefully utilize as many bandwidth as they can get. These applications are said to have elastic bandwidth requirements; most applications currently running on LANs (local area networks) have elastic bandwidth requirements. Service classes which support elastic applications are known as xe2x80x9cbest effortxe2x80x9d in the Internet community and available bit rate (ABR) in the Broadband ISDN/ATM community. Another set of service classes support real-time applications such as circuit emulation and video. Real-time applications may require data be transmitted through the network with bounded jitter (e.g., packet delay variation. These applications are said to have inelastic or real-time bandwidth requirements. For a general discussion of these topics, see Shenker, xe2x80x9cFundamental Design Issues for the Future Internet,xe2x80x9d IEEE Journal on Selected Areas in Communications (JSAC), Vol. 13, No. 7, September, 1995, pp. 1176-1188.
Asynchronous Transfer mode (ATM) switching is becoming an accepted mechanism for providing sufficient peak and aggregate bandwidths to support the aforementioned applications as well as supporting multiple service classes. Many ATM switches are currently implemented with first-in first-out (FIFO) queuing which is known to exhibit pathological behavior when used for ABR traffic. For a discussion of the same issues in the Internet context, see Floyd and Jacobson, xe2x80x9cOn Traffic Phase Effects in Packet-Switched Gateways,xe2x80x9d Internetworking: Research and Experience, Vol. 3, pp. 115-156 (1992); and Zhang et al., xe2x80x9cObservations on the Dynamics of a Congestion Control Algorithm: The Effects of Two-Way Traffic,xe2x80x9d ACM SIGCOMM 91 Conference, Sep. 3-6, 1991, Zurich, Switzerland, pp 133-148. Further, because FIFO queuing does not provide isolation, it is unable to protect correctly behaving applications against misbehaving applications.
Weighted fair queuing can be used to provide bounded jitter (packet delay variation) for real-time packet communications. See Parekh, xe2x80x9cA Generalized Processor Sharing Approach to Flow Control in Integrated Service Networks,xe2x80x9d Ph.D. thesis, Department of Electrical Engineering and Computer Science, MIT (1992). Recent results have also established delay bounds for systems using the closely related mechanisms of virtual clock and self-clocked fair queuing. See Goyal et al., xe2x80x9cDetermining End-to-End Delay Bounds in Heterogeneous Networks,xe2x80x9d in Proceedings of the 5th International Workshop on Network and Operating System Support for Digital Audio and Video (NOSSDAV), Durham, N.H., Apr. 18-22, 1995.
Weighted fair queuing is also known to provide excellent service for ABR or xe2x80x9cbest effortxe2x80x9d service classes. Some of the original work on fair queuing was motivated by a desire to avoid the pathologies of FIFO-based queuing. See Christopher Lefelhocz, Bryan Lyles, Scott Shenker, Lixia Zhang, xe2x80x9cCongestion Control for Best Effort Service: why we need a new paradigm,xe2x80x9d IEEE Network Magazine, January 1996, for a general discussion of mechanisms for the elastic service classes.
As a result, non-FIFO queuing mechanisms such as weighted fair queuing and approximations to fair queuing such as round-robin have been suggested as a means of allocating bandwidth in conventional packet-switched networks. See, for example, Demors et al., xe2x80x9cAnalysis and Simulation of a Fair Queuing Algorithm,xe2x80x9d in Proceedings of ACM SIGCOMM, pp. 1-12, (1989); and Hahne, xe2x80x9cRound-Robin Scheduling for Max-Min Fairness in Data Networks,xe2x80x9d IEEE Journal on Selected Areas in Communications, Vol. 9, pp. 1024-1039 (1991).
In conventional packet-switched networks, data packets arrive at a switch (e.g., the head-end controller or, more generally, a bandwidth allocation unit) before bandwidth for its subsequent transmission to a destination terminal equipment (or, more generally, a network access unit) has been allocated. In these systems, therefore, there is no logical separation between a data packet and a request for transmission. Shared-media networks, in contradistinction, logically, physically, and temporally separate a data packet""s request for transmission and its actual transmission.
Thus, a need to allocate bandwidth, fairly, and dynamically, in a shared-media packet switched network such as conventional hybrid fiber-coax television network exists. Such bandwidth allocation should accommodate both elastic and inelastic applications.
The invention relates to a method to allocate bandwidth, fairly and dynamically, in a shared-media packet switched network, which accommodates both elastic and inelastic applications. The method is directed at allocating bandwidth transmission slots between a terminal equipment 210 (or more generally a network access unit 315) and a head-end controller 105 (or more generally a bandwidth allocation unit 305) in a shared-media network (e.g., the network 300). Specifically, the inventive method manipulates requests for transmission bandwidth received by a bandwidth allocation unit from a network access unit, converting the arriving requests into virtual scheduling times for granting access to the shared media. Further, the inventive scheme supports multiple quality of service (QoS) classes via mechanisms which give highest priority to the service class with the most stringent QoS requirements.
If a bandwidth allocation unit 305 associates a time-stamp with a request for bandwidth from a network access unit 315, either a weighted fair queuing algorithm or a virtual clock algorithm may be used to generate a sequence of upstream slot/transmission assignment grants which the bandwidth allocation unit 305 can transmit downstream to the requesting network access unit 315. Time stamps can be derived from requests for bandwidth and thereafter used to generate transmission time-slots in which the actual packets can be transmitted. Use of weighted fair queuing or virtual clock algorithms allow tight jitter bounds to be placed on a network""s inelastic service, while use of weighted fair queuing is known to provide excellent service for elastic applications.
This idea can be extended to include requests from a network access unit 315 consisting of a batch of transmission requests; one request for each packet to be transmitted. Further, requests can be made either in terms of a rate (e.g., xe2x80x9cplease give me 100 packets-per-secondxe2x80x9d), or in terms of a burst (e.g., xe2x80x9cI have 20 packets queued up ready to sendxe2x80x9d).
In addition, a request may contain a single information element which represents an aggregation of individual queued transmission requests (e.g., a single summary request representing the request status of the collection of transmission queues at the network access unit); or a request may contain multiple information elements, a batch which represents a burst size worth of requests over one or more transmission queues at the network access unit. The implementation for either scheme in the bandwidth allocation unit can use a simple counter per network access unit which is incremented when a request is received by the bandwidth allocation unit and decremented when an authorization grant is issued by the bandwidth allocation unit.
Moreover, for guaranteed rate-based service, a proxy request generator at the bandwidth allocation unit may be used which issues a virtual service request on behalf of the network access unit for the specific rate of the service.
FIG. 1 is a block diagram of a hybrid fiber-coax cable television communications network.
FIG. 2 is a block diagram of virtual upstream and downstream communication channels in a shared-media network.
FIG. 3 is a block diagram of generic communications network.
FIG. 4 is a high-level block diagram of the information flows between the bandwidth allocation unit and a single network access unit.
FIGS. 5 and 6 are pseudocode program listings.